package poj;

import util.PrintArray;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 最短循环子串 Poj 2046
 * Created by shuowu on 2018/1/13.
 */
public class MinRepeatSubString2046 {

    public static void main(String[] args){
        MinRepeatSubString2046 object = new MinRepeatSubString2046();
        System.out.println(object.getMinRepeat("aabaab"));
    }

    //定理：假设S的长度为len，则S存在循环子串，当且仅当，len可以被len - next[len - 1]整除，最短循环子串为S[len - next[len - 1]]
    // 最大循环次数n为len/(len - next[len - 1])，否则为1
    // 可以很容易地证明能整除 ——> 是重复串
    // 但是当时死脑筋，想证明 不是重复串 ——> 不能整除
    // 这是一个逆否命题啊，根本不用证明啊
    // 当且仅当是指的两个命题互为充要条件
    // 只需要证明重复串 ——> 能整除即可
    public void getNext(int[] array, String mode) {
        if (mode == null || array.length < mode.length()) {
            return;
        }
        int k = 0;
        char[] string = mode.toCharArray();
        for (int index = 1; index < array.length; index++) {
            if (string[index] == string[k]) {
                array[index] = array[index - 1] + 1;
                k++;
            } else {
                while (k  > 0 && string[index] != string[k]){
                    k = array[k - 1];
                }
                if (string[index] == string[k]) {
                    k++;
                }
                array[index] = k;
            }
        }
    }

    //获取字符串最短重复字符的重复次数比如aaaa ,a重复了4次
    public int getMinRepeat(String string){
        if(string == null || string.length() <= 0){
            return 0;
        }
        int length = string.length();
        int[] array = new int[length];
        getNext(array, string);
        PrintArray.printArray(array);
        if (length % (length - array[length - 1]) != 0) {
            return 1;
        }
        return length / (length - array[length - 1]);
    }

}
